<?php
/**
 * @title 37. 解数独 - 排序+递归
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param String[][] $board
     * @return NULL
     */
    function solveSudoku(&$board) {
        /**
         * @since 2020-09-15 可选范围
         */
        $tmp = [];
        for ($i=1; $i<=9; $i++){
            $tmp[$i] = strval($i);
        }
        $tmp = array_fill(0, 9, $tmp);
        $ranges = [
            "row" => $tmp,
            "column" => $tmp,
            "area" => $tmp,
        ];
        // return $tmp;

        /**
         * @since 2020-09-15 未确定数组
         */
        $list = [];

        /**
         * @since 2020-09-15 已存在标记
         */
        for ($row=0; $row<=8; $row++){
            for($column=0; $column<=8; $column++){
                /**
                 * @since 2020-09-15 所属区域
                 */
                $area = intval($row/3)*3 + intval($column/3);

                /**
                 * @since 2020-09-15 存在标记
                 */
                $val = $board[$row][$column];
                if($val != "."){
                    unset($ranges["row"][$row][$val]);
                    unset($ranges["column"][$column][$val]);
                    unset($ranges["area"][$area][$val]);
                } else {
                    $list[] = [$row, $column, $area];
                }
            }
        }
        // return $ranges;

        /**
         * @return
         */
        return self::find($board, $ranges, $list);
    }

    /**
     * @title 递归数独结果
     * @author start2004
     * @since 2020-09-15 Created
     *
     * @param array $board
     * @param array $exists
     * @param array $ranges
     * @return array
     */
    public function find(&$board = [], $ranges = [], $list = []){
        /**
         * @since 2020-09-15 可选范围数量
         */
        $datas = [];
        foreach($list as $l) {
            list($row, $column, $area) = $l;
            $vals = array_intersect($ranges["row"][$row], $ranges["column"][$column], $ranges["area"][$area]);
            $count = count($vals);
            if($count == 0){
                return false;
                break;
            } else {}
            $datas[$count][] = $l;
        }

        /**
         * @since 2020-09-15 可选范围从少到多遍历
         */
        $list = [];
        for ($i=9; $i>=1; $i--){
            if(isset($datas[$i])){
                $list = array_merge($list, $datas[$i]);
            } else {}
        }

        /**
         * @since 2020-09-15 抛出最后一个值, 选择最少的
         */
        $data = array_pop($list);
        if($data === null){
            return $board;
        } else {
            list($row, $column, $area) = $data;

            /**
             * @since 2020-09-15 3者交集
             */
            $vals = array_intersect($ranges["row"][$row], $ranges["column"][$column], $ranges["area"][$area]);
            if($vals){
                foreach ($vals as $val){
                    /**
                     * @since 2020-09-15 赋值
                     */
                    $board[$row][$column] = $val;

                    /**
                     * @since 2020-09-15 范围上, 剔除该值
                     */
                    $r = $ranges;
                    unset($r["row"][$row][$val]);
                    unset($r["column"][$column][$val]);
                    unset($r["area"][$area][$val]);

                    /**
                     * @since 2020-09-15 继续尝试匹配
                     */
                    $result = self::find($board, $r, $list);
                    if($result !== false){
                        return $result;
                        break;
                    } else {}
                }
            } else {}

            /**
             * @return
             */
            return false;
        }
    }
}

/**
 * @url http://127.0.0.1/leetcode/202009/2020.09.15_2.php
 */
$datas = [
    [
        [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]],
    ],
    [
        [[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]],
    ],
    [
        [[".","2","6","5",".",".",".","9","."],["5",".",".",".","7","9",".",".","4"],["3",".",".",".","1",".",".",".","."],["6",".",".",".",".",".","8",".","7"],[".","7","5",".","2",".",".","1","."],[".","1",".",".",".",".","4",".","."],[".",".",".","3",".","8","9",".","2"],["7",".",".",".","6",".",".","4","."],[".","3",".","2",".",".","1",".","."]],
    ],
    [
        [[".",".",".","2",".",".",".","6","3"],["3",".",".",".",".","5","4",".","1"],[".",".","1",".",".","3","9","8","."],[".",".",".",".",".",".",".","9","."],[".",".",".","5","3","8",".",".","."],[".","3",".",".",".",".",".",".","."],[".","2","6","3",".",".","5",".","."],["5",".","3","7",".",".",".",".","8"],["4","7",".",".",".","1",".",".","."]],
    ],
    [
        [["1",".",".",".","7",".",".","3","."],["8","3",".","6",".",".",".",".","."],[".",".","2","9",".",".","6",".","8"],["6",".",".",".",".","4","9",".","7"],[".","9",".",".",".",".",".","5","."],["3",".","7","5",".",".",".",".","4"],["2",".","3",".",".","9","1",".","."],[".",".",".",".",".","2",".","4","3"],[".","4",".",".","8",".",".",".","9"]],
    ],
    [
        [[".",".",".",".",".","7",".",".","9"],[".","4",".",".","8","1","2",".","."],[".",".",".","9",".",".",".","1","."],[".",".","5","3",".",".",".","7","2"],["2","9","3",".",".",".",".","5","."],[".",".",".",".",".","5","3",".","."],["8",".",".",".","2","3",".",".","."],["7",".",".",".","5",".",".","4","."],["5","3","1",".","7",".",".",".","."]],
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->solveSudoku(...$data);
    // $result = $obj->find(...$data);
    var_dump($result);

    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". $data[1][$i][0] ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
